package l.l.w.CodingInterviews;


import java.util.ArrayList;
import java.util.Arrays;

/**
 * Created by llw on 2018/3/24/0024.
 */
public class 字符串的排列 {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        if(str == null || str.length() == 0) return result;
        StringBuilder sb = new StringBuilder(str.length());
        char[] chars = str.toCharArray();
        permutationStr(chars, result, 0);
        return result;
    }
    private void permutationStr(char[] chars,ArrayList<String> result,int i){
        if(i == chars.length ){
            result.add(new String(chars));
            return;
        }
        char [] visited = new char[chars.length];
        Arrays.sort(chars,i,chars.length);
        for(int j = i;j< chars.length;++j){
            char cur = chars[j];
            if(!visit(visited,cur)){
                visited[j - i] = cur;
                exchange(chars,j,i);
                permutationStr(Arrays.copyOf(chars,chars.length),result,i+1);
                exchange(chars,j,i);
            }
        }
    }
    private void exchange(char[] chars,int j, int i){
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
    }
    private boolean visit(char[] chars,char c){
        for(int i = 0; i < chars.length; ++i){
            if(chars[i] == c) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        java.lang.String a = "abc";
        ArrayList<String> result = new 字符串的排列().Permutation(a);
        System.out.println(result);
    }
}
